1. Field of the Invention
The present invention relates to network communications and, more specifically, to allocating resources for use in network communications.
2. Background Information
A computer network is a geographically distributed collection of interconnected subnetworks for transporting data between network nodes, such as computers. A local area network (LAN) is an example of such a subnetwork. The network's topology is defined by an arrangement of client nodes that communicate with one another, typically through one or more intermediate network nodes, such as routers or switches. As used herein, a client node is a network node that is configured to originate or terminate communications over the network. In contrast, an intermediate network node is a node that facilitates routing data between client nodes. Communications between network nodes are typically effected by exchanging discrete packets of data according to predefined protocols. In this context, a protocol consists of a set of rules defining how the nodes interact with each other.
The data packets transferred among the network nodes may include fixed-sized data cells and/or variable-sized data frames. Each data packet typically comprises “payload” data prepended (“encapsulated”) by at least one network header formatted in accordance with a network communication protocol. The network headers include information that enables the client nodes and intermediate nodes to route the packet efficiently through the computer network. Often, a packet's network headers include at least a data-link (layer 2) header and an internetwork (layer 3) header, as defined by the Open Systems Interconnection (OSI) Reference Model. The OSI Reference Model is generally described in more detail in Section 1.1 of the reference book entitled Interconnections Second Edition, by Radia Perlman, published Sep. 1999, which is hereby incorporated by reference as though fully set forth herein.
In operation, a client node may send a data packet to a network interface of an intermediate network node. Thereafter, the intermediate network node receives the packet and forwards the packet to its next destination. For example, the intermediate network node may perform a layer-2 switching function that simply re-directs the packet from one network interface to another based on the contents of the packet's data-link header. Alternatively, the intermediate network node may perform a layer-3 routing function, or forwarding decision, that selects the most appropriate network interface to forward the packet based on the contents of the packet's internetwork header.
Data packets are used to transport many forms of information, including voice and video information, over networks and subnetworks. For instance, voice information may be transmitted in accordance with the Voice over Internet Protocol (VoIP). VoIP refers to a group of technologies used to transmit voice information over data networks from a source node to a destination node. The source and destination nodes employ voice agents that convert voice information from its traditional telephony form to a form that is suitable for packet transmission. In other words, the source node's voice agent encodes, compresses, and encapsulates the voice information into a plurality of data packets, and the destination node's voice agent performs complementary functions to de-encapsulate, uncompress, and decode the VoIP packets. Examples of voice agents include IP telephones, VoIP gateways, certain private branch exchanges (PBXs), personal computers (PCs) running communication applications, network devices providing voice gateway services, etc.
A source node (sender) may be configured to transfer a unidirectional stream of data packets, or a “data flow,” to a destination node (receiver) in a data network. The data flow may comprise, for example, data or voice information. The data flow is unidirectional in that data travels one-way from the sender to the receiver. The logical procession of network nodes that transmit and receive data packets from the sender to the receiver defines the data flow's data path. A first node that is nearer the receiver in the data flow's data path than a second node in the flow is said to be “downstream” from the second node. Likewise, a first node that is nearer the sender in the data flow's path than a second node in the flow is said to be “upstream” from the second node. As used herein, a “flow” and a “path” may be used interchangeably herein, as will be understood by those skilled in the art. Notably, some applications, such as certain voice communications, require data flows in two opposing directions (bi-directional). In other words, a first data flow may transport one caller's voice from node A to node B, and a second (opposing) data flow may carry the voice data of the other participant from node B to node A. In this case, loss of either of the data flows may render the telephone call useless. Such bi-directional data flows are often referred to as a “duplex.”
Some data flows are associated with a certain level of quality of service (QoS). For example, a data flow's QoS may specify minimum end-to-end latency or bandwidth requirements needed to support the flow. The Resource reSerVation Protocol (RSVP) is a network-control protocol that enables source and destination nodes to “reserve” the necessary resources to establish the data flow in accordance with the flow's required QoS. RSVP works in conjunction with routing protocols to, e.g., reserve resources along a data flow between the source and destination nodes to establish a level of QoS required by the data flow. RSVP is defined in R. Braden, et al., “Resource ReSerVation Protocol (RSVP),” Request For Comments (RFC) 2205, which is hereby incorporated by reference as though fully set forth herein.
In a typical arrangement, the sender sends an RSVP Path message identifying itself and indicating the minimum bandwidth needed to receive the data flow. The Path message proceeds to the receiver through the data flow, and each intermediate network node may update an optional “Adspec” object of the Path message. The Adspec object contains, inter alia, information about the properties of the data flow, such as available services, delay, and bandwidth estimates. Adspec objects may be generated by senders or by intermediate nodes, and are modified as they travel from one node to another. An Adspec object advertises the possible service parameters composed of the properties of all previous-hop nodes upstream. Namely, the arriving Adspec object is combined with the node's own parameters and service conditions, and then forwarded to the next node. A receiver can use the Adspec information to predict the end-to-end QoS, to choose the most appropriate service and to scale its QoS request according to the current possibilities of the network. If any node along the flow is unable to meet the minimum QoS value (e.g., bandwidth), the node may send a Path Error (PathErr) message to the sender, or may continue to forward with Path message with an Adspec object indicating the potential failure conditions.
The receiver receives the Path message and may first determine whether the data flow can support the requested resources based on the contents of the optional Adspec object in the Path message. If the flow can be supported, (or if no Adspec object is found in the Path message) the receiver responds with a “request for resources” in the form of an RSVP reservation request (Resv message) which travels hop-by-hop back to the sender. Within the Resv message is a “FlowSpec” object, which contains, inter alia, an indication of a peak expected traffic value (e.g., bandwidth) from the sender (Tspec), and the requested traffic value to be reserved (Rspec). At each hop, the corresponding intermediate network node sets aside (“assigns” ) sufficient resources to provide the requested bandwidth for the desired data flow. These assigned resources are consequently made available to the data flow so that the data packets of the flow get appropriate QoS treatment.
If sufficient resources are not available, an intermediate network node may “reject” the Resv message (i.e., does not continue forwarding it), generate a reserve error (ResvErr) message, and forward the ResvErr message downstream over the flow to the destination node. The destination node eventually receives the ResvErr message and concludes that the reservation has failed. A destination node whose Resv message has been rejected may later re-attempt to acquire the resources by re-transmitting another Resv message. Source nodes are unaffected by this process, and they continue to send Path messages to refresh their state.
As defined in RFC 2205, an RSVP data flow is “admitted” and resources allocated to the data flow using a capacity-based admission control technique. According to this technique, resources are allocated to data flows on a “first-come-first-admitted” basis until the capacity of the resources is exhausted. S. Herzog, “RSVP Extensions for Policy Control,” RFC 2750, which is hereby incorporated by reference as though fully set forth herein, defines an extension to RFC 2205 that incorporates policy-based admission control. Through this extension to RSVP, admission control involves reserving resources on a policy basis in addition to using capacity as a basis. A simple example of such is an authentication/authorization policy. If a person attempts to reserve bandwidth but is unknown to the administration or makes an unauthorized request, the request will be denied based on the authentication/authorization policy even though bandwidth is available. But among authorized requestors, bandwidth is granted on a first-come-first-admitted basis.
A policy often employed in conjunction with RFC 2750 is a preemption-priority-based policy described in S. Herzog, “Signaled Preemption Priority Policy Element,” RFC 3181, which is hereby incorporated by reference as though fully set forth herein. The preemption-priority-based policy incorporates a technique that allows a new reservation to preempt one or more existing lower priority reservations in order to acquire resources reserved for the lower priority reservations. According to the technique, a preemption-priority value is associated with a new reservation and defending-priority values are associated with respective existing reservations. The reservations' preemption and defending priority values may be assigned in various ways known in the art. The preemption-priority value for the new reservation is compared with the defending-priority values of existing reservations to determine if the new reservation “preempts” any existing lower priority reservations. If so, resources allocated to selected lower priority reservations are reallocated for the new reservation.
In practice, a Resv message either contains the preemption-priority value associated with the new reservation or a default preemption-priority value is assigned to the reservation request if it does not already contain one. A network node that receives the Resv message may first determine if sufficient unallocated resources are immediately available to satisfy the resources requested in the Resv message. If not, the node then may identify lower priority existing reservations that may be preempted to meet the needs of the new reservation. This may be done by comparing the new reservation's preemption priority value with the defending priority value of an existing reservation to determine if the new reservation is higher in priority than the existing reservation. If so, the network node may preempt the existing reservation by “tearing it down” and reallocating the resources associated with the torn down reservation to the new reservation. Thereafter, a ResvErr message is sent downstream along the data flow to notify the downstream nodes, including the destination node, of the preemption.
One problem with the above-described preemption technique is that it may cause lower priority reservations to be unnecessarily preempted, thus, causing unnecessary disruption to data flows associated with these reservations. For example, if a new reservation fails due to, e.g., an upstream node not having sufficient resources for the new reservation, downstream nodes that have already preempted lower priority reservations to allocate resources to the new reservation have unnecessarily disrupted the data flows associated with the preempted reservations. In addition, to “reclaim” the resources lost due to preemption, the lower priority reservations would have to be re-established, thus causing the data flows to incur further disruption.
A method to solve this problem is described in commonly-owned copending U.S. patent application Ser. No. 10/875,985, entitled METHOD FOR IMPROVING RSVP-BASED PREEMPTION, filed by Dhesikan et al., on Jun. 24, 2004, the contents of which are hereby incorporated by reference in its entirety. The method described therein first marks lower priority reservations for preemption, and waits until it is determined that all nodes along the flow are able to comply with the Path request, and that the flow should not otherwise fail. Once the sender receives notice (e.g., in a Resv message) that all intermediate nodes can comply (i.e., with available or preemptable resources), the sender transmits a Reservation Confirmation (ResvConf) message downstream to the receiver. When each intermediate node receives the ResvConf message, it then preempts any necessary reservations that were previously marked.
Another problem associated with the above-described preemption technique is that it may cause unnecessary preemptions in the event a lower-priority reservation is granted and is substantially immediately preempted by another reservation with a higher priority. This situation forces the lower-priority reservation to tear down the connection, and attempt to create a new flow, causing extra signaling and potentially non-user friendly results. Also, the lower priority reservations may have had alternative options available, such as, e.g., alternative routes in the network, or other known network protocols. In addition, the above-described preemption technique unnecessarily preempts reservations during certain duplex reservations, such as where a first flow in a first direction preempts reservations only to have a second flow in a second direction fail. As noted above, a failure of one of the two bi-directional flows in a duplex renders the duplex essentially useless; hence the preemptions for the first flow were unnecessary.